"""
315. 计算右侧小于当前元素的个数
"""
from typing import List


class Nums:

    def __init__(self, index, value):
        self.index = index
        self.value = value


class Solution:

    def __init__(self):
        self.res = []
        self.tmp: List[Nums] = []

    """
     * 利用归并排序,
     * 归并排序时，在每次合并有序数组时，如果右子树值小于右子树时，即nums[i] = tmp[j++]时，n结果就是[mid + 1, j)，即：j - mid - 1
     * 有个问题，由于i的位置上一直在变，而且一直刷新，所以需要记录原始位置：做法，定义一个内部类Nums，将题目转换为对Nums[]数组进行排序，每次更新数量值
    """

    def countSmaller(self, nums: List[int]) -> List[int]:
        # 将nums封装为Nums数组
        nums1 = [Nums(i, nums[i]) for i in range(len(nums))]
        self.res = [0 for i in range(len(nums))]
        self.tmp = [0 for i in range(len(nums))]
        self.gbSort(nums1, 0, len(nums) - 1)

        return self.res

    """
     * 归并排序
     * 归并排序可以理解为二叉树，先将左子树排序，再将右子树排序，最后再将左右子树合并排序
     * 如何将数组分解为二叉树，以中心点为分割线，将数组分解为二叉树，叶子结点为数组元素
    """

    def gbSort(self, nums: List[Nums], low, high):
        if low == high:
            return

        # 中心点
        mid = low + int((high - low) / 2)

        # 排序左子树
        self.gbSort(nums, low, mid)
        # 排序右子树
        self.gbSort(nums, mid + 1, high)

        # 合并两个有序数组
        self.mergin_nums(nums, low, mid, high)

    def mergin_nums(self, nums: List[Nums], low, mid, high):
        i = low
        j = mid + 1
        for k in range(low, high + 1):
            self.tmp[k] = nums[k]

        # 开始合并
        k = low
        while i <= mid or j <= high:
            if i > mid:
                nums[k] = self.tmp[j]
                j += 1
            elif j > high:
                nums[k] = self.tmp[i]
                i += 1
                self.res[nums[k].index] += j - mid - 1
            elif self.tmp[i].value <= self.tmp[j].value:
                nums[k] = self.tmp[i]
                i += 1
                self.res[nums[k].index] += j - mid - 1
            else:
                nums[k] = self.tmp[j]
                j += 1
            k += 1
